package com.mystudy.leetcode.problem.tree.p_897;

import com.mystudy.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: infoalgorithm
 * @description: 递增顺序查找树
 * @author: zhouzhilong
 * @create: 2019-07-24 16:27
 **/
public class Solution {

    public TreeNode increasingBST(TreeNode root) {
        //先中序遍历
        List<TreeNode> list = new ArrayList<>();
        inOrder(root,list);
        for (TreeNode treeNode : list) {
            System.out.println(treeNode.val);
        }
        //再重新生成树
        TreeNode newRoot = null;
        for (TreeNode treeNode : list) {
            newRoot = add(newRoot, treeNode);
        }


        return newRoot;
    }

    private void inOrder(TreeNode node, List<TreeNode> list){
        if(node == null){
            return;
        }
        inOrder(node.left,list);
        list.add(node);
        inOrder(node.right,list);
    }


    private TreeNode add(TreeNode root,TreeNode node){
        node.left =null;
        node.right = null;
        if(root == null){
            return node;
        }

        root.right =  add(root.right,node);
        return root;
    }

}
